<!DOCTYPE html>



  


<html class="theme-next mist use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/blog/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/blog/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/blog/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/blog/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/blog/images/favicon-new.jpg?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/blog/images/favicon-new.jpg?v=5.1.4">


  <link rel="mask-icon" href="/blog/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="redis,数据结构,">










<meta name="description" content="Redis是一种key/value型数据库，其中，每个key和value都是使用对象表示的。 对象类型和编码Redis使用对象来表示数据库中的键和值，每次创建一个键值对时，都会至少创建两个对象，一个对象用来保存键值对的键，另一个对象用作键值对的值。每个对象都有一个redisObject结构表示: 1234567891011121314151617181920typedef struct redis">
<meta name="keywords" content="redis,数据结构">
<meta property="og:type" content="article">
<meta property="og:title" content="Redis数据结构与对象">
<meta property="og:url" content="https://lenoy.gitee.io/blog/Redis_structure.html">
<meta property="og:site_name" content="Lenoy聆羽">
<meta property="og:description" content="Redis是一种key/value型数据库，其中，每个key和value都是使用对象表示的。 对象类型和编码Redis使用对象来表示数据库中的键和值，每次创建一个键值对时，都会至少创建两个对象，一个对象用来保存键值对的键，另一个对象用作键值对的值。每个对象都有一个redisObject结构表示: 1234567891011121314151617181920typedef struct redis">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="https://lenoy.gitee.io/blog/Redis_structure/1.png">
<meta property="og:image" content="https://lenoy.gitee.io/blog/Redis_structure/2.png">
<meta property="og:image" content="https://lenoy.gitee.io/blog/Redis_structure/3.png">
<meta property="og:image" content="https://lenoy.gitee.io/blog/Redis_structure/4.png">
<meta property="og:image" content="https://lenoy.gitee.io/blog/Redis_structure/5.png">
<meta property="og:image" content="https://lenoy.gitee.io/blog/Redis_structure/6.png">
<meta property="og:image" content="https://lenoy.gitee.io/blog/Redis_structure/7.png">
<meta property="og:image" content="https://lenoy.gitee.io/blog/Redis_structure/8.png">
<meta property="og:updated_time" content="2021-11-12T09:57:40.057Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Redis数据结构与对象">
<meta name="twitter:description" content="Redis是一种key/value型数据库，其中，每个key和value都是使用对象表示的。 对象类型和编码Redis使用对象来表示数据库中的键和值，每次创建一个键值对时，都会至少创建两个对象，一个对象用来保存键值对的键，另一个对象用作键值对的值。每个对象都有一个redisObject结构表示: 1234567891011121314151617181920typedef struct redis">
<meta name="twitter:image" content="https://lenoy.gitee.io/blog/Redis_structure/1.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/blog/',
    scheme: 'Mist',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://lenoy.gitee.io/blog/Redis_structure.html">





  <title>Redis数据结构与对象 | Lenoy聆羽</title>
  








</head>

<body itemscope="" itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope="" itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/blog/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Lenoy聆羽</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">刘超的个人博客，java开发工程师</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/blog/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/blog/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/blog/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br>
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lenoy.gitee.io/blog/blog/Redis_structure.html">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="liuchao">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/blog/images/head.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Lenoy聆羽">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">Redis数据结构与对象</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2020-09-29T00:00:00+08:00">
                2020-09-29
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/Redis/" itemprop="url" rel="index">
                    <span itemprop="name">Redis</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>Redis是一种key/value型数据库，其中，每个key和value都是使用对象表示的。</p>
<h3 id="对象类型和编码"><a href="#对象类型和编码" class="headerlink" title="对象类型和编码"></a>对象类型和编码</h3><p>Redis使用对象来表示数据库中的键和值，每次创建一个键值对时，都会至少创建两个对象，一个对象用来保存键值对的键，另一个对象用作键值对的值。<br>每个对象都有一个redisObject结构表示:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">redisObject</span> &#123;</span>  </span><br><span class="line">	<span class="comment">// 类型  </span></span><br><span class="line">	<span class="keyword">unsigned</span> type:<span class="number">4</span>;          </span><br><span class="line"></span><br><span class="line">	<span class="comment">// 不使用(对齐位)  </span></span><br><span class="line">	<span class="keyword">unsigned</span> notused:<span class="number">2</span>;  </span><br><span class="line"></span><br><span class="line">	<span class="comment">// 编码方式  </span></span><br><span class="line">	<span class="keyword">unsigned</span> encoding:<span class="number">4</span>;  </span><br><span class="line"></span><br><span class="line">	<span class="comment">// LRU 时间（相对于 server.lruclock）  </span></span><br><span class="line">	<span class="keyword">unsigned</span> lru:<span class="number">22</span>;  </span><br><span class="line"></span><br><span class="line">	<span class="comment">// 引用计数  </span></span><br><span class="line">	<span class="keyword">int</span> refcount;  </span><br><span class="line"></span><br><span class="line">	<span class="comment">// 指向对象的值  </span></span><br><span class="line">	<span class="keyword">void</span> *ptr;  </span><br><span class="line">	  </span><br><span class="line">&#125; robj;</span><br></pre></td></tr></table></figure>
<ul>
<li><p>类型<br>表示这个对象是5钟类型中的哪一种，他们通常使用类型常量来标记：</p>

<table>
    <thead>
    <tr>
        <th>类型常量</th>
        <th>对象的名称</th>
    </tr>
    </thead>
    <tbody>
    <tr>
        <td>REDIS_STRING</td>
        <td>字符串对象</td>
    </tr>
    <tr>
        <td>REDIS_LIST</td>
        <td>列表对象</td>
    </tr>
    <tr>
        <td>REDIS_HASH</td>
        <td>哈希对象</td>
    </tr>
    <tr>
        <td>REDIS_SET</td>
        <td>集合对象</td>
    </tr>
    <tr>
        <td>REDIS_ZSET</td>
        <td>有序集合对象</td>
    </tr>
    </tbody>
</table>

</li>
<li><p>编码和底层实现<br>表示底层实现的数据结构，也就是ptr指针指向的底层数据结构，也是用常量来表示，底层数据编码方式共有八种，如下所示：</p>

<table>
    <thead>
    <tr>
        <th>编码常量</th>
        <th>编码所对应的底层数据结构</th>
    </tr>
    </thead>
    <tbody>
    <tr>
        <td>REDIS_ENCODING_INT</td>
        <td>long 类型的整数</td>
    </tr>
    <tr>
        <td>REDIS_ENCODING_EMBSTR</td>
        <td>embstr 编码的简单动态字符串</td>
    </tr>
    <tr>
        <td>REDIS_ENCODING_RAW</td>
        <td>简单动态字符串</td>
    </tr>
    <tr>
        <td>REDIS_ENCODING_HT</td>
        <td>字典</td>
    </tr>
    <tr>
        <td>REDIS_ENCODING_LINKEDLIST</td>
        <td>双端链表</td>
    </tr>
    <tr>
        <td>REDIS_ENCODING_ZIPLIST</td>
        <td>压缩列表</td>
    </tr>
    <tr>
        <td>REDIS_ENCODING_INTSET</td>
        <td>整数集合</td>
    </tr>
    <tr>
        <td>REDIS_ENCODING_SKIPLIST</td>
        <td>跳跃表和字典</td>
    </tr>
    </tbody>
</table>

</li>
<li><p>每种类型都至少可以使用两种不同的编码，也就是说，type表示当前是哪一种对象，encoding表示当前对象的底层实现，他们之间的对应关系如下图所示（比如String对象类型可以是INT，EMBSTR或者RAW三种编码实现）：</p>

<table>
    <thead>
    <tr>
        <th>类型</th>
        <th>编码</th>
        <th>对象</th>
    </tr>
    </thead>
    <tbody>
    <tr>
        <td>REDIS_STRING</td>
        <td>REDIS_ENCODING_INT</td>
        <td>使用整数值实现的字符串对象</td>
    </tr>
    <tr>
        <td>REDIS_STRING</td>
        <td>REDIS_ENCODING_EMBSTR</td>
        <td>用embstr编码的简单动态字符串实现的字符串对象</td>
    </tr>
    <tr>
        <td>REDIS_STRING</td>
        <td>REDIS_ENCODING_RAW</td>
        <td>使用简单动态字符串实现的字符串对象</td>
    </tr>
    <tr>
        <td>REDIS_LIST</td>
        <td>REDIS_ENCODING_ZIPLIST</td>
        <td>使用压缩列表实现的列表对象</td>
    </tr>
    <tr>
        <td>REDIS_LIST</td>
        <td>REDIS_ENCODING_LINKEDLIST</td>
        <td>使用双链表实现的列表对象</td>
    </tr>
    <tr>
        <td>REDIS_HASH</td>
        <td>REDIS_ENCODING_ZIPLIST</td>
        <td>使用压缩列表实现的哈希对象</td>
    </tr>
    <tr>
        <td>REDIS_HASH</td>
        <td>REDIS_ENCODING_HT</td>
        <td>使用字典实现的哈希对象</td>
    </tr>
    <tr>
        <td>REDIS_SET</td>
        <td>REDIS_ENCODING_INTSET</td>
        <td>使用整数集合实现的集合对象</td>
    </tr>
    <tr>
        <td>REDIS_SET</td>
        <td>REDIS_ENCODING_HT</td>
        <td>使用字典实现的集合对象</td>
    </tr>
    <tr>
        <td>REDIS_ZSET</td>
        <td>REDIS_ENCODING_ZIPLIST</td>
        <td>使用压缩列表实现的有序集合对象</td>
    </tr>
    <tr>
        <td>REDIS_ZSET</td>
        <td>REDIS_ENCODING_SKIPLIST</td>
        <td>使用跳跃表和字典实现的有序集合对象</td>
    </tr>
    </tbody>
</table>

</li>
</ul>
<h4 id="简单动态字符串（SDS）"><a href="#简单动态字符串（SDS）" class="headerlink" title="简单动态字符串（SDS）"></a>简单动态字符串（SDS）</h4><p>Redis的简单动态字符串，通常被用来存储字符串值，几乎所有的字符串类型都是SDS的。另外，SDS还常被用作缓冲区（buffer）：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区等，都是由SDS实现的。</p>
<p>Redis里面很多地方都用到了字符串，我们知道redis是一个键值对存储的非关系型数据库，那么所有的key都是用字符串存储的，还有字符串类型，这些都是用字符串存储的。甚至包括序列化操作Dump和Restore，也是将对象序列化为字符串之后好进行数据的传输。<br>Redis的底层是C++实现的，我们知道C++的字符串是一个以\0结尾的char数组，字符串的长度为数组长度-1，但是redis并没有直接使用C++的char数组，而是自己实现了一个简单的结构，这个结构的名字叫做简单动态字符串（simple dynamic string）。这个结构的定义如下：<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">sdshdr</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> len;</span><br><span class="line">    <span class="keyword">int</span> <span class="built_in">free</span>;</span><br><span class="line">    <span class="keyword">int</span> buf[];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>sdshdr就是简单动态字符串的结构。</p>
<ul>
<li>len：字符串的长度，是buf数组已使用的字节的数量。这样的话获取字符串长度的时间复杂度是常数，也就是O(1)。</li>
<li>free：是buf数组中未使用的字节的数量。</li>
<li>buf：用来存储字符串的数组，这个存储的字符串不包含最后的\0结尾。</li>
</ul>
<p>SDS可以自动的对数组容量进行修改，完成自动扩容。比如进行字符串拼接操作，这个时候buf数组容量不够的时候，若buf数组小于1MB大小，会对buf数组的容量扩容到原来的两倍，如果大于1MB，那么程序会分配1MB的free空间。</p>
<h4 id="双端链表（LINKEDLIST）"><a href="#双端链表（LINKEDLIST）" class="headerlink" title="双端链表（LINKEDLIST）"></a>双端链表（LINKEDLIST）</h4><p>Redis的链表由链表和链表节点构成。链表封装了链表节点，提供相关操作API，链表节点则封装了每个节点的数据等相关信息。链表节点的数据结构：<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">listNode</span>&#123;</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">listNode</span> *<span class="title">prev</span>;</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">listNode</span> *<span class="title">next</span>;</span></span><br><span class="line">    <span class="keyword">void</span> *value;</span><br><span class="line">&#125;listNode;</span><br></pre></td></tr></table></figure></p>
<p>从中我们可以看到，链表节点持有三个变量，前两个变量是两个分别指向上一个和下一个节点的指针，value变量存储了节点的值（多态存储）。<br>虽然使用ListNode可以实现一个简单的链表，但是Redis还是使用list结构来封装所有的操作，这样操作起来会更方便。<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">list</span>&#123;</span></span><br><span class="line">    listNode *head;</span><br><span class="line">    listNode *tail;</span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">long</span> len;</span><br><span class="line">    <span class="keyword">void</span> *(*dup) (<span class="keyword">void</span> *ptr)</span><br><span class="line">    <span class="keyword">void</span> *(*<span class="built_in">free</span>)(<span class="keyword">void</span> *ptr)</span><br><span class="line">    <span class="keyword">int</span> (*match)(<span class="keyword">void</span> *ptr,<span class="keyword">void</span> *key);</span><br><span class="line">&#125;<span class="built_in">list</span>;</span><br></pre></td></tr></table></figure></p>
<p>这个list结构封装了头结点，尾节点和链表的长度以及若干操作，包括赋值操作，释放操作以及节点对比的操作。而且，这是一个双向无环链表，而且是多态的。</p>
<h4 id="字典（HT）"><a href="#字典（HT）" class="headerlink" title="字典（HT）"></a>字典（HT）</h4><p>Redis数据库本身就是使用字典来实现的。<br>字典的结构从高层到底层实现分别是：字典（dict），字典哈希表（dictht），哈希表节点（dictEntry）。<br>哈希表（dictht）：<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">dictht</span>&#123;</span></span><br><span class="line">    <span class="comment">//哈希表数组</span></span><br><span class="line">    dictEntry **table;</span><br><span class="line">    <span class="comment">//哈希表大小</span></span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">long</span> size;</span><br><span class="line">    <span class="comment">//哈希表大小掩码，</span></span><br><span class="line">    <span class="comment">//总是等于size-1,</span></span><br><span class="line">    <span class="comment">//用于计算索引值</span></span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">long</span> sizemask;</span><br><span class="line">    <span class="comment">//该哈希表已有的节点的数量</span></span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">long</span> used;</span><br><span class="line">&#125;dictht;</span><br></pre></td></tr></table></figure></p>
<p>哈希表节点（dictEntry）:<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">dictEntry</span>&#123;</span></span><br><span class="line">    <span class="comment">//键</span></span><br><span class="line">    <span class="keyword">void</span> *key;</span><br><span class="line">    <span class="comment">//值</span></span><br><span class="line">    <span class="keyword">union</span>&#123;</span><br><span class="line">        <span class="keyword">void</span> *val;</span><br><span class="line">        <span class="keyword">unit64_t</span> u64;</span><br><span class="line">        <span class="keyword">int64_t</span> s64;</span><br><span class="line">    &#125; v;</span><br><span class="line">    <span class="comment">//指向下个哈希表节点，形成链表</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">dictEntry</span> *<span class="title">next</span>;</span></span><br><span class="line"> </span><br><span class="line">&#125;dictEntry;</span><br></pre></td></tr></table></figure></p>
<p>可以看到，这个哈希表的结构使用的是拉链法来实现的， 拉链法既可以实现基本的哈希表结构，也能用来避免冲突。<br>字典（dict）：<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">dict</span>&#123;</span></span><br><span class="line">    <span class="comment">//类型特定函数</span></span><br><span class="line">    dictType *type;</span><br><span class="line">    <span class="comment">//私有数据</span></span><br><span class="line">    <span class="keyword">void</span> *privdata;</span><br><span class="line">    <span class="comment">//哈希表</span></span><br><span class="line">    dictht ht[<span class="number">2</span>]</span><br><span class="line">    <span class="comment">//rehash索引</span></span><br><span class="line">    <span class="comment">//当rehash不在进行时，值为-1</span></span><br><span class="line">    <span class="keyword">int</span> trehashidx;</span><br><span class="line">&#125;dict;</span><br></pre></td></tr></table></figure></p>
<p>ht数组有两个元素，每一个都是一个dictht哈希表，dicht[0]是用于真正存放数据，dicht[1]一般在哈希表元素过多进行rehash的时候用于中转数据。<br>dictht中的table用于真正存放元素，每个key/value对用一个dictEntry表示，放在dictEntry数组中。<br><img src="/blog/Redis_structure/1.png"></p>
<h5 id="redis字典的哈希算法"><a href="#redis字典的哈希算法" class="headerlink" title="redis字典的哈希算法"></a>redis字典的哈希算法</h5><p>哈希算法比较简单，采用的是按位与的操作，首先使用dict的type的一个函数hashFunction（key）对key计算一个hash值，然后将这个哈希值和字典的某个哈希表dictht的sizemask按位与计算出索引位置。<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">#使用字典设置的哈希函数，计算键key的哈希值</span><br><span class="line">hash=dict—&gt;type—&gt;hashFunction(key);</span><br><span class="line"></span><br><span class="line">#使用哈希表的sizemask属性和哈希值，计算出索引值</span><br><span class="line">#根据情况不同，ht[x]可以是ht[<span class="number">0</span>]或者ht[<span class="number">1</span>]</span><br><span class="line">index=hash &amp; dict—&gt;ht[x].sizemask;</span><br></pre></td></tr></table></figure></p>
<ul>
<li>再散列Rehash<br>redis的字典随着不断的增加（减少）元素，会导致装载因子慢慢的变大（变小），这个时候需要调整数组ht数组的大小，调整的基本方式是：</li>
</ul>
<ol>
<li>为字典的ht[1]分配空间，然后分情况讨论：<br>如果是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方<br>如果是缩小操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的n次方</li>
<li>分配完空间后，那么就是将ht[0]上面的数据移动到ht[1]上面去了，这个移动的过程中还是需要前面的哈希算法计算索引值，将数据移动到新的索引上。</li>
<li>接下来，回收ht[0]的空间，然后将ht[1]设置为ht[0],ht[0]设置为ht[1]。<br>但是当数据量非常大的时候，rehash是一件非常消耗时间的操作，如果单纯的按上面的流程进行再散列，那么会导致系统的响应延迟非常高。</li>
</ol>
<ul>
<li>渐进式Rehash<br>渐进式rehash在上面的rehash的基础上，进行了改进，改进过后的步骤将rehash的过程变得不在那么占用cpu时间，详细的步骤如下：</li>
</ul>
<ol>
<li>为ht[1]分配空间，让字典同时拥有ht[0]和ht[1]</li>
<li>在字典中维持一个索引计数器变量rehashidx，将它的值设置为0，表示rehash工作正在进行。</li>
<li>在rehash执行期间，每次对字典的增删改查，程序完成了执行指定的操作之外，还会将ht[0]的哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx的属性值增加1。</li>
<li>这样随着操作不断进行，rehasidx不断的增加1，不断的将ht[0]中的索引为0，1，2，3，上面的元素rehash到ht[1]中，在一定的时间之后，所有元素都被rehash到ht[1]，rehash结束，这个时候就将rehashidx设置为-1，表示rehash操作完成。</li>
</ol>
<h4 id="跳跃表（SKIPLIST）"><a href="#跳跃表（SKIPLIST）" class="headerlink" title="跳跃表（SKIPLIST）"></a>跳跃表（SKIPLIST）</h4><p>跳跃表实现了有序集合中的快速查找，在大多数情况下它的速度都可以和平衡树差不多。面分别是跳跃表skiplist和它内部的节点skiplistNode的结构体：<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/* </span></span><br><span class="line"><span class="comment"> * 跳跃表 </span></span><br><span class="line"><span class="comment"> */</span>  </span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">zskiplist</span> &#123;</span>  </span><br><span class="line">    <span class="comment">// 头节点，尾节点  </span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistNode</span> *<span class="title">header</span>, *<span class="title">tail</span>;</span>  </span><br><span class="line">    <span class="comment">// 节点数量  </span></span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">long</span> length;  </span><br><span class="line">    <span class="comment">// 目前表内节点的最大层数  </span></span><br><span class="line">    <span class="keyword">int</span> level;  </span><br><span class="line">&#125; zskiplist;  </span><br><span class="line"><span class="comment">/* ZSETs use a specialized version of Skiplists */</span>  </span><br><span class="line"><span class="comment">/* </span></span><br><span class="line"><span class="comment"> * 跳跃表节点 </span></span><br><span class="line"><span class="comment"> */</span>  </span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistNode</span> &#123;</span>  </span><br><span class="line">    <span class="comment">// member 对象  </span></span><br><span class="line">    robj *obj;  </span><br><span class="line">    <span class="comment">// 分值  </span></span><br><span class="line">    <span class="keyword">double</span> score;  </span><br><span class="line">    <span class="comment">// 后退指针  </span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistNode</span> *<span class="title">backward</span>;</span>  </span><br><span class="line">    <span class="comment">// 层  </span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistLevel</span> &#123;</span>  </span><br><span class="line">        <span class="comment">// 前进指针  </span></span><br><span class="line">        <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistNode</span> *<span class="title">forward</span>;</span>  </span><br><span class="line">        <span class="comment">// 这个层跨越的节点数量  </span></span><br><span class="line">        <span class="keyword">unsigned</span> <span class="keyword">int</span> span;  </span><br><span class="line">    &#125; level[];  </span><br><span class="line">&#125; zskiplistNode;</span><br></pre></td></tr></table></figure></p>
<img src="/blog/Redis_structure/2.png">
<h4 id="整数集合（INTSET）"><a href="#整数集合（INTSET）" class="headerlink" title="整数集合（INTSET）"></a>整数集合（INTSET）</h4><p>整数集合时集合键的底层实现之一，当一个集合只包含整数值元素，并且集合元素不多时，就可以使用整数集合来作为集合键的底层实现。整数集合可以保存类型Int16_t,int32_t或者int64_t的整数值，并且因为是集合，所以不会出现重复元素。<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">intset</span>&#123;</span></span><br><span class="line">    <span class="comment">//编码方式</span></span><br><span class="line">    <span class="keyword">uint32_t</span> enconding;</span><br><span class="line">    <span class="comment">//集合包含的元素数量</span></span><br><span class="line">    <span class="keyword">uint32_t</span> length;</span><br><span class="line">    <span class="comment">//保存元素的数组</span></span><br><span class="line">    <span class="keyword">int8_t</span> contents[];</span><br><span class="line">&#125;intset;</span><br></pre></td></tr></table></figure></p>
<ul>
<li>encoding：这是一个无符号32位整数，表示整数集合数组contents存储到的数据类型是Int16_t,int32_t或者int64_t</li>
<li>length：也是一个无符号32位整数，表示contents存储的元素的个数。</li>
<li>contents：一个数组，并且里面的数据按照从大到小的元素排列。并且存储的类型由encoding决定，而不是它本身的类型int8_t。</li>
</ul>
<p>当一个整数集合元素存储的都是int16_t或者int32_t的时候，这个时候如果放入一个位数比较大，超过16位或者32位，就会有引起整数数组的升级操作，升级操作的基本过程如下：</p>
<ol>
<li>先根据新元素的大小，拓展数组contents的空间。</li>
<li>将contents数组中的元素转换成新元素相同的类型，并放到正确的位置上（维持有序性）。</li>
<li>将新元素添加到新的contents数组里，由于这个新元素会引起数组升级，一般是比原来的数要大或者要小，所以要么添加到尾部，要么添加到头部。</li>
</ol>
<h4 id="压缩列表（ZIPLIST）"><a href="#压缩列表（ZIPLIST）" class="headerlink" title="压缩列表（ZIPLIST）"></a>压缩列表（ZIPLIST）</h4><p>压缩列表是列表和哈希的底层实现之一，它的好处是更能节省内存空间，因为它所存储的内容都是在连续的内存区域当中的。当一个列表只包含少量的列表项，且列表项是小整数值或者较短的字符串时，Redis就会使用压缩列表。整个ziplist只需要malloc一次，它们在内存中是一块连续的区域。<br>但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性，插入的复杂度是O(N)，即每次插入都会重新进行realloc。<br>另外，当一个哈希只包含少量键值对，并且每个键值对的键和值是小整数值或者长度比较短的字符串，那么Redis机会使用压缩列表来做哈希键的底层实现。<br>压缩里列表的结构：<br><img src="/blog/Redis_structure/3.png"><br>
<table>
    <thead>
    <tr>
        <th>属性</th>
        <th>类型</th>
        <th>长度</th>
        <th>用途</th>
    </tr>
    </thead>
    <tbody>
    <tr>
        <td>zlbytes</td>
        <td>ulnt32_t</td>
        <td>4字节</td>
        <td>记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配或者计算zlend的位置时使用</td>
    </tr>
    <tr>
        <td>zltail</td>
        <td>uint32_t</td>
        <td>4字节</td>
        <td>记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无須遍历整个压列表就可以确定表尾节点的地址</td>
    </tr>
    <tr>
        <td>zllen</td>
        <td>uint16_t</td>
        <td>2字节</td>
        <td>记录了压列表包含的节点数量：当这个属性的值小于UINT16_MAX（65535）时，这个属性的值就是压缩列表包含节点的数量．当这个值等于UINT16_MAX时，节点的真实数量需要遍历整个压列表才能计箅得出</td>
    </tr>
    <tr>
        <td>entryX</td>
        <td>列表节点</td>
        <td>不定</td>
        <td>压缩列表包含的各个节点，节点的长度由节点保存的内容决定</td>
    </tr>
    <tr>
        <td>zlend</td>
        <td>uint8_t</td>
        <td>1字节</td>
        <td>特殊值OxFF（十进制255)，用于标记压缩列表的末端</td>
    </tr>
    </tbody>
</table>
<br>压缩列表是一个总是从尾部开始遍历的列表。因为zlbytes和zltail可以计算得到表尾，然后entryX的特殊结构又能使我们按照一定的顺序从表尾遍历我们的压缩列表。</p>
<h5 id="列表节点"><a href="#列表节点" class="headerlink" title="列表节点"></a>列表节点</h5><p>每个压缩列表节点可以保存一个字节数组或者一个整数值，其中字节数组可以是以下三种长度的其中一种：</p>
<ul>
<li>长度小于等于63（2廴]）字节的字节数组；</li>
<li>长度小于等于16383（21）字节的字节数组；</li>
<li>长度小于等于4294967295（产一1）字节的字节数组；</li>
</ul>
<p>而整数值则可以是以下六种长度的其中一种：</p>
<ul>
<li>4位长，介于0至12之间的无符号整数；</li>
<li>1字节长的有符号整数；</li>
<li>3字节长的有符号整数；</li>
<li>int16_t类型整数；</li>
<li>int32_t类型整数；</li>
<li>int64_t类型整数。</li>
</ul>
<p>每个压缩列表节点都由previousentrylength、encoding、content三个部分组成：<br><img src="/blog/Redis_structure/4.png"></p>
<ul>
<li>previous_entry_length:以字节为单位，表示前一个列表节点的字节长度。如果前一个列表节点的长度小于254字节，那么这个属性只需要占用8位（1字节）的空间，如果前一个节点的长度大于254字节，那么这个属性就会占用5字节，其中第一个字节是固定值254，后面4个字节用于表示前一节点的长度。</li>
<li>encoding记录了content数组所保存的数据的类型以及长度。不同的编码表示不同的类型以及长度。比如00、01、10开头的表示字节数组，11开头的表示整数编码，分别表示content存储的内容是字节数组还是整数。</li>
<li>content数组记录了保存的内容。</li>
</ul>
<p>previous_entry_length属性都记录了前一个节点的长度，如果前一个节点长度小于254，那么previous_entry_length长度为1个字节，否则就是5个字节。这样在插入节点或者删除节点时，就有可能导致该节点之后的所有节点更新previous_entry_length属性，这叫做连锁更新。<br>连锁更新会导致n次空间重分配，每次空间分配的最坏复杂度为O（n），也就导致了O(n^2)的复杂度。但是这种情况并不常见，所以Redis并没有对这种情况做特殊处理。</p>
<h3 id="Redis对象"><a href="#Redis对象" class="headerlink" title="Redis对象"></a>Redis对象</h3><h4 id="字符串（String）"><a href="#字符串（String）" class="headerlink" title="字符串（String）"></a>字符串（String）</h4><p>字符串对象的编码可以是int，raw或者embstr。</p>
<ul>
<li>int：如果我们设定了一个字符串对象，它保存的是整数值，并且这个整数值可以用long类型来表示，那么我们就可以使用int编码，同时让ptr指针指向一个long。</li>
<li>raw:如果一个字符串对象保存的是一个字符串值，而且这个字符串的长度大于32字节，那么就必须使用一个简单动态字符串来保存这个字符串值，编码设置为raw。</li>
<li>embstr:embstr是用来保存长度小于32字节的字符串的。embstr和raw的区别是，embstr在创建字符串对象的时候，会分配一次空间，这个空间包含redisObject对象结构和sdshdr结构（保存字符串），而raw则会进行两次分配，分表分配空间给redisObject和sdshdr。所以在字符串较短时，使用embstr会有一些优势：分配次数降低，释放次数降低（因为只需要释放一个空间，而raw需要释放两个空间），字符串连续。</li>
<li>浮点数也是以字符串类型来保存的。只不过使用的时候再转化为浮点类型进行计算</li>
<li>特殊情况下，int和embstr会转化成raw编码的字符串对象。比如对int编码的字符串对象执行了APPEND操作，使得数字不能再用long雷兴表示或者添加了字符不在是数字等。int不会转为embstr，只会变成raw。同时embstr是只读的，只要对embstr修改，就会转换成raw。</li>
</ul>
<h4 id="列表（List）"><a href="#列表（List）" class="headerlink" title="列表（List）"></a>列表（List）</h4><p>列表对象的编码可以是双端链表（linkedlist）或者压缩列表（ziplist）。<br>如果列表使用压缩列表来存储元素，那么结构就如下所示：<br><img src="/blog/Redis_structure/5.png"><br>如果使用的是双端链表，那么结构图如下所示：<br><img src="/blog/Redis_structure/6.png"></p>
<p>当列表对象同时满足下面的两个的两个条件时，列表对象使用ziplist编码：</p>
<ul>
<li>当列表对象保存的所有字符串的元素长度都小于64字节。</li>
<li>列表对象保存的元素数量小于512个。</li>
</ul>
<p>不满足这两个条件的，需要使用linkedlist。<br>当一个列表对象的编码是ziplist，随着元素的增多或者修改某一个元素，导致不满足上面的两个条件的时候，就需要编码转换操作将ziplist转化为linkedlist。</p>
<p>List除了可以直接作为列表存储来使用，还可以作为一个队列使用，另外，list还支持阻塞的方式从一端取值，来达到阻塞队列的使用。</p>
<h4 id="哈希对象（Hash）"><a href="#哈希对象（Hash）" class="headerlink" title="哈希对象（Hash）"></a>哈希对象（Hash）</h4><p>哈希对象的编码可以是ziplist或者hashtable。<br>如果是ziplist，哈希对象每次都是将键值对两个对象加入到ziplist的尾部，先将键添加到ziplist的尾部，再将值添加到ziplist的尾部，这样每次都会放入两个值。如下图所示：<br><img src="/blog/Redis_structure/7.png"><br>如果是hashtable，由于这是一个字典，因此键值对直接就保存到里面了，如下图所示：<br><img src="/blog/Redis_structure/8.png"></p>
<p>和列表一样，在保存的键值对较为简单的情况下，优先使用ziplist。使用ziplist必须满足下列两个条件：</p>
<ul>
<li>哈希对象保存的键值对的键和值的长度都小于64字节。</li>
<li>哈希对象保存的键值对数量小于512个。</li>
</ul>
<p>不满足以上情况的，需要使用hashtable。<br>当一个底层编码是ziplist的hash对象不满足上述两个条件时，就会引起向hashtable编码的转换，这就是编码转换。</p>
<h4 id="集合（Set）"><a href="#集合（Set）" class="headerlink" title="集合（Set）"></a>集合（Set）</h4><p>集合对象的编码可以是intset或者hashtable。<br>当一个集合里面的对象都是整数，且元素数量不超过512时，底层的实现就是整数集合，否则底层就用hashtable实现。<br>如果底层是hashtable，这个时候这个字典没有值，只是键。由于键是没有重复的，所以，就能保证集合的无重复的性质。<br>当然，对于集合，也存在编码转换的过程，原理和前面的一致。</p>
<h4 id="有序集合（ZSet）"><a href="#有序集合（ZSet）" class="headerlink" title="有序集合（ZSet）"></a>有序集合（ZSet）</h4><p>有序集合的编码可以是ziplist和skiplist。<br>对于ziplist，底层使用压缩列表作为实现，每个集合元素用两个紧挨在一起的压缩列表节点来保存，第一个保存集合元素的成员，迭戈元素保存元素的分值。按照分值大小，分值较小的放到压缩列表的表头方向，分值较大的放到压缩列表的表尾方向。<br>对于skiplist编码，底层是用zset结构作为底层实现，而这个zset包含一个字典和一个跳跃表，如下所示：<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">zset</span>&#123;</span></span><br><span class="line">    zskiplist *zsl;</span><br><span class="line">    dict *dict;</span><br><span class="line">&#125;zset;</span><br></pre></td></tr></table></figure></p>
<p>zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的object保存了元素的成员，而score保存了元素的分值，利用这个跳跃表，可以对有序集合进行范围型操作，比如ZRANK，ZRANGE等命令。除此之外，dickt字典为有序集合创建了一个从成员到分值的映射，字典中的每一个键值对都保存了一个几何元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值，通过这个字典，程序可以用常数复杂度来查找给定成员的分值，比如ZSCORE命令。<br>同时使用zskiplist和dict原因是为了效率，不同的操作可以使用不同的结构。而元素成员和分值可以通过指针在两个结构之间连接起来，对空间的占用也不会浪费很多，因此效率很高。<br>当有序集合同时满足下列两个条件时，使用ziplist编码，否则使用skiplist编码：</p>
<ul>
<li>有序集合保存的元素数量小于128个。</li>
<li>所有元素成员的长度小于64字节。</li>
</ul>
<p>zset具有根据score来排序存储数据的作用。比如可以每次更新数据，都不删除旧数据，而是把新数据存储下来，使用当前时间戳作为score的值，在取值的时候直接取最新的值作为当前值返回。这样可以在需要的时候找到这个值的历史记录。另外，zset还可以作为排行榜使用。</p>
<h4 id="基数统计（HyperLogLog）"><a href="#基数统计（HyperLogLog）" class="headerlink" title="基数统计（HyperLogLog）"></a>基数统计（HyperLogLog）</h4><p>HyperLogLog结构可以非常省内存的去统计各种计数，比如注册ip数、每日访问IP数、页面实时UV（PV肯定字符串就搞定了）、在线用户数等。<br>这个数据结构的特点就是，可以比较准确的估算出你要统计的数量，但是却无法知道统计的详细内容。但是HyperLogLog在Redis中每个键占用的内存都是12K，对于大量的数据统计来说，将会非常节省内存。<br>HyperLogLog是一个基于HLL算法（一种基于概率和统计实现的基数估计算法）实现的结构，用于统计一组数据集合中不重复的数据个数，只能比较准确的估算出基数，可以使用少量固定的内存去存储并识别集合中的唯一元素。而且这个估算的基数并不一定准确，是一个带有 0.81% 标准错误（standard error）的近似值。</p>
<h5 id="PFADD"><a href="#PFADD" class="headerlink" title="PFADD"></a>PFADD</h5><p>添加指定元素到 HyperLogLog 中。<br>在执行这个命令之后，如果 HyperLogLog 内部的基数估算发生了变化，那么就会返回1，否则（认为已经存在）就返回0。<br>这个命令的时间复杂度为O(1)</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">PFADD  count_201901  <span class="string">"10.10.10.1"</span>  <span class="string">"10.10.10.2"</span>  <span class="string">"10.10.10.3"</span></span><br><span class="line">(integer) <span class="number">1</span></span><br><span class="line">PFADD  count_201901 <span class="string">"10.10.10.2"</span>  <span class="string">"10.10.10.4"</span>  <span class="string">"10.10.10.5"</span>  # 存在就只加新的</span><br><span class="line">(integer) <span class="number">1</span></span><br><span class="line">PFADD  count_201901 <span class="string">"10.10.10.2"</span>  # 存在就不会增加</span><br><span class="line">(integer) <span class="number">0</span></span><br></pre></td></tr></table></figure>
<h5 id="PFCOUNT"><a href="#PFCOUNT" class="headerlink" title="PFCOUNT"></a>PFCOUNT</h5><p>返回指定 HyperLogLog 的基数估算值。<br>当命令作用于单个键的时候，返回这个键的基数估算值。如果键不存在，则返回0。<br>当作用于多个键的时候，返回这些键的并集估算值。类似于把这些键都合并了之后，在调用这个命令输出。<br>这个命令在作用于单个值的时候，时间复杂度为O(1)，并且具有非常低的平均常数时间；在作用于N个值的时候，时间复杂度为O(N)</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">PFADD  count_201901  <span class="string">"10.10.10.1"</span>  <span class="string">"10.10.10.2"</span>  <span class="string">"10.10.10.3"</span></span><br><span class="line">(integer) <span class="number">1</span></span><br><span class="line">PFCOUNT  count_201901</span><br><span class="line">(integer) <span class="number">3</span></span><br><span class="line">PFADD  count_201902  <span class="string">"10.10.10.1"</span>  <span class="string">"10.10.10.4"</span>  <span class="string">"10.10.10.5"</span></span><br><span class="line">(integer) <span class="number">1</span></span><br><span class="line">PFCOUNT  count_201901  count_201902</span><br><span class="line">(integer) <span class="number">5</span></span><br></pre></td></tr></table></figure>
<h5 id="PFMERGE"><a href="#PFMERGE" class="headerlink" title="PFMERGE"></a>PFMERGE</h5><p>合并多个 HyperLogLog 为一个 HyperLogLog。<br>这个命令的第一个参数为目标键，剩下的参数为要合并的HyperLogLog。命令执行时，如果目标键不存在，则创建后再执行合并。<br>这个命令的时间复杂度为O(N)，其中N为要合并的HyperLogLog的个数。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">PFADD  count_201901  <span class="string">"10.10.10.1"</span>  <span class="string">"10.10.10.2"</span>  <span class="string">"10.10.10.3"</span></span><br><span class="line">(integer) <span class="number">1</span></span><br><span class="line">PFADD  count_201902  <span class="string">"10.10.10.1"</span>  <span class="string">"10.10.10.4"</span>  <span class="string">"10.10.10.5"</span></span><br><span class="line">(integer) <span class="number">1</span></span><br><span class="line">PFMERGE count_2019   count_201901   count_201902</span><br><span class="line">OK</span><br><span class="line">PFCOUNT  count_2019</span><br><span class="line">(integer) <span class="number">5</span></span><br></pre></td></tr></table></figure>
<h3 id="类型检查和命令多态"><a href="#类型检查和命令多态" class="headerlink" title="类型检查和命令多态"></a>类型检查和命令多态</h3><p>Redis命令可以分为两种类型，其中一种可以对任何类型的键执行，比如说DEL命令，EXPIRE命令，RENAME名理工，TYPE命令，OBJECT命令等。另一种命令只能对待特定类型的键执行，比如：</p>
<ul>
<li>SET、GET、APPEND、STRLEN等命令只能对字符串键执行；</li>
<li>HDEL、HSET、HGET、HLE等命令只能对哈希键执行；</li>
<li>RPUSH、LOPO、LINSERT、LLEN等命令只能对列表建执行；</li>
<li>SADD、SPOP、SINTER、SCARD等命令只能对集合键执行；</li>
<li>ZADD、ZCARD、ZRANK、ZSCORE等命令只能对有序集合键执行；</li>
</ul>
<p>对于特定类型的命令，Redis会先检查输入键的类型是否正确，然后在确定是否执行给定的命令，这就是<strong>类型检查</strong>。而类型检查是通过redisObject的type属性来实现的。</p>
<p>由于不同的对象有不同的实现type，而不同的type对应不同的底层实现，比如你对一个键执行LLEN命令，除了要进行前面的类型检查以外，Redis会根据不同的实现方式encoding，选择不同的操作接口去获得长度，这就是<strong>命令多态</strong>。</p>
<h3 id="内存回收"><a href="#内存回收" class="headerlink" title="内存回收"></a>内存回收</h3><p>Redis在对象系统中构建了一个引用计数计数来实现内存回收。也就是说，redisObject对象中的refcount的变量就是用来引用计数的：</p>
<p>当创建一个对象时，引用计数的值会被初始化为1；<br>当对象被一个新程序使用时，它的引用计数的值会增1；<br>当对象不再被一个程序使用时，它的引用计数的值会减1；<br>当对象的引用计数为0时，对象所占用的内存会被释放。</p>
<p><strong>对象共享</strong></p>
<p>在创建一个对象A，为它赋值100，然后再创建一个对象B，也赋值100的时候，这个时候Redis就会让B共享同一个字符串100，节约内存的使用。</p>

      
    </div>
    
    
    
    <div>
      
        <div>
    
        <div style="text-align:center;color: #ccc;font-size:16px;">--------------<i class="fa fa-paw"></i>本文结束<i class="fa fa-paw"></i>--------------</div>
    
</div>
      
    </div>
    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div>觉得文章不错就打赏一下哟~~~</div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/blog/images/wechatpay.png" alt="liuchao 微信支付">
        <p>微信支付</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/blog/images/alipay.png" alt="liuchao 支付宝">
        <p>支付宝</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    
      <div>
        <ul class="post-copyright">
<!--
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    liuchao
  </li>
-->
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://lenoy.gitee.io/blog/Redis_structure.html" title="Redis数据结构与对象">https://lenoy.gitee.io/blog/Redis_structure.html</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/blog/tags/redis/" rel="tag"><i class="fa fa-tag"></i> redis</a>
          
            <a href="/blog/tags/数据结构/" rel="tag"><i class="fa fa-tag"></i> 数据结构</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/blog/JVM_tuning_parameters.html" rel="next" title="JVM调优及实用参数">
                <i class="fa fa-chevron-left"></i> JVM调优及实用参数
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/blog/Redis_process.html" rel="prev" title="Redis单线程原理">
                Redis单线程原理 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope="" itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/blog/images/head.jpg" alt="liuchao">
            
              <p class="site-author-name" itemprop="name">liuchao</p>
              <p class="site-description motion-element" itemprop="description">好记性不如烂笔头，记下来，迈出去</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/blog/archives/">
              
                  <span class="site-state-item-count">62</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/blog/categories/index.html">
                  <span class="site-state-item-count">12</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                
                  <span class="site-state-item-count">83</span>
                  <span class="site-state-item-name">标签</span>
                
              </div>
            

          </nav>

          

          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#对象类型和编码"><span class="nav-number">1.</span> <span class="nav-text">对象类型和编码</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#简单动态字符串（SDS）"><span class="nav-number">1.1.</span> <span class="nav-text">简单动态字符串（SDS）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#双端链表（LINKEDLIST）"><span class="nav-number">1.2.</span> <span class="nav-text">双端链表（LINKEDLIST）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#字典（HT）"><span class="nav-number">1.3.</span> <span class="nav-text">字典（HT）</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#redis字典的哈希算法"><span class="nav-number">1.3.1.</span> <span class="nav-text">redis字典的哈希算法</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#跳跃表（SKIPLIST）"><span class="nav-number">1.4.</span> <span class="nav-text">跳跃表（SKIPLIST）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#整数集合（INTSET）"><span class="nav-number">1.5.</span> <span class="nav-text">整数集合（INTSET）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#压缩列表（ZIPLIST）"><span class="nav-number">1.6.</span> <span class="nav-text">压缩列表（ZIPLIST）</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#列表节点"><span class="nav-number">1.6.1.</span> <span class="nav-text">列表节点</span></a></li></ol></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Redis对象"><span class="nav-number">2.</span> <span class="nav-text">Redis对象</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#字符串（String）"><span class="nav-number">2.1.</span> <span class="nav-text">字符串（String）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#列表（List）"><span class="nav-number">2.2.</span> <span class="nav-text">列表（List）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#哈希对象（Hash）"><span class="nav-number">2.3.</span> <span class="nav-text">哈希对象（Hash）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#集合（Set）"><span class="nav-number">2.4.</span> <span class="nav-text">集合（Set）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#有序集合（ZSet）"><span class="nav-number">2.5.</span> <span class="nav-text">有序集合（ZSet）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#基数统计（HyperLogLog）"><span class="nav-number">2.6.</span> <span class="nav-text">基数统计（HyperLogLog）</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#PFADD"><span class="nav-number">2.6.1.</span> <span class="nav-text">PFADD</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#PFCOUNT"><span class="nav-number">2.6.2.</span> <span class="nav-text">PFCOUNT</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#PFMERGE"><span class="nav-number">2.6.3.</span> <span class="nav-text">PFMERGE</span></a></li></ol></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#类型检查和命令多态"><span class="nav-number">3.</span> <span class="nav-text">类型检查和命令多态</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#内存回收"><span class="nav-number">4.</span> <span class="nav-text">内存回收</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2017 &mdash; <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-id-card"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">liuchao</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Mist</a></div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/blog/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/blog/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/blog/js/src/motion.js?v=5.1.4"></script>



  
  

  
  <script type="text/javascript" src="/blog/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/blog/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/blog/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/blog/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  

  

  

  

</body>
</html>
<!-- 页面点击小红心 -->
<script type="text/javascript">
  !function(e,t,a){function n(){c(".heart{width: 10px;height: 10px;position: fixed;background: #f00;transform: rotate(45deg);-webkit-transform: rotate(45deg);-moz-transform: rotate(45deg);}.heart:after,.heart:before{content: '';width: inherit;height: inherit;background: inherit;border-radius: 50%;-webkit-border-radius: 50%;-moz-border-radius: 50%;position: fixed;}.heart:after{top: -5px;}.heart:before{left: -5px;}"),o(),r()}function r(){for(var e=0;e<d.length;e++)d[e].alpha<=0?(t.body.removeChild(d[e].el),d.splice(e,1)):(d[e].y--,d[e].scale+=.004,d[e].alpha-=.013,d[e].el.style.cssText="left:"+d[e].x+"px;top:"+d[e].y+"px;opacity:"+d[e].alpha+";transform:scale("+d[e].scale+","+d[e].scale+") rotate(45deg);background:"+d[e].color+";z-index:99999");requestAnimationFrame(r)}function o(){var t="function"==typeof e.onclick&&e.onclick;e.onclick=function(e){t&&t(),i(e)}}function i(e){var a=t.createElement("div");a.className="heart",d.push({el:a,x:e.clientX-5,y:e.clientY-5,scale:1,alpha:1,color:s()}),t.body.appendChild(a)}function c(e){var a=t.createElement("style");a.type="text/css";try{a.appendChild(t.createTextNode(e))}catch(t){a.styleSheet.cssText=e}t.getElementsByTagName("head")[0].appendChild(a)}function s(){return"rgb("+~~(255*Math.random())+","+~~(255*Math.random())+","+~~(255*Math.random())+")"}var d=[];e.requestAnimationFrame=function(){return e.requestAnimationFrame||e.webkitRequestAnimationFrame||e.mozRequestAnimationFrame||e.oRequestAnimationFrame||e.msRequestAnimationFrame||function(e){setTimeout(e,1e3/60)}}(),n()}(window,document);
</script>
